【题解】 [国家集训队]聪聪可可 树形DP luoguP2634 | Qiuly's blog!

【题解】 [国家集训队]聪聪可可 树形DP luoguP2634

Posted on | Edited on | In | Comments:

别人都说，什么淀粉质啊之类的轻松水过，然而我有码量恐惧症，不适合如此数据结构(主要也是太弱了QvQ)

那就上树形DP吧！

$f[i][j]$表示点i为根的子树中到i路径权值和%3=j的点数.

状态转移：Dfs，直接从子树转移即可，具体看代码。

真是炒鸡简单的啦~~

CODE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A")
using namespace std;
const int N=2e4+2;
inline ll gcd(int x,int y){return y?gcd(y,x%y):x;}
struct Edge{int nxt,to,val;}G[N<<2];
int n,cnt,head[N];ll f[N][3],ans;
template <typename _Tp> inline void IN(_Tp&x){
	char ch;bool flag=0;x=0;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	if(flag)x=-x;
}
inline void add(int x,int y,int v){
	G[++cnt].nxt=head[x],G[cnt].to=y,G[cnt].val=v,head[x]=cnt;
	G[++cnt].nxt=head[y],G[cnt].to=x,G[cnt].val=v,head[y]=cnt;
}
inline void Dfs(int x,int fa){
	f[x][0]=1;
	for(register int i=head[x];i;i=G[i].nxt){
		int y=G[i].to;if(y==fa)continue;Dfs(y,x);
		for(int j=0;j<3;++j)ans+=(ll)(f[y][j]*f[x][(((3-j-G[i].val)%3)+3)%3]*2);
        //从子树转移过来，注意取模，看不懂的同学画图秒懂
		for(int j=0;j<3;++j)f[x][(G[i].val+j)%3]+=f[y][j];
        //跟新 f[x]
	}return;
}
int main(){
    IN(n);ll s=(ll)n*n,g;
    for(register int x,y,v,i=1;i<n;++i)
       IN(x),IN(y),IN(v),add(x,y,v);
    Dfs(1,0);ans+=n,g=gcd(ans,s);//一定要是最简分数
    printf("%lld/%lld\n",ans/g,s/g);//输出答案
	return 0;
}

本文标题:【题解】 [国家集训队]聪聪可可 树形DP luoguP2634

文章作者:Qiuly

发布时间:2019年03月10日 - 00:00

最后更新:2019年05月05日 - 11:53

原始链接:http://qiulyblog.github.io/2019/03/10/[题解]luoguP2634/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。